Graphs can be used to model large data sets in numerous fields, such as physics, computer science, biology and sociology. In particular, graphs can represent networks, i.e. systems with pairwise relations among their elements. The identification of recurrent patterns in these relations can provide valuable insight in the dynamics of a system. Therefore there is a need for a fast and reliable identification of so-called network motifs in networks, namely those patterns whose occurrence is statistically significant. The computational process of detecting patterns in large data sets on standard central processing unit (CPU)-based architectures and graphics processor unit (GPU)-based architectures is very time and energy consuming.
There are frameworks like GraphGen by Nurvitadhi et al. presented in 2014 or the Graphlet Counting Case Study by Betkaoui et al. in 2011 that generate specific data processing engines for particular graph operations. However, they are not application tailored and cover a broad range of graph problems instead of optimizing the performance for motif detection.
It is an object of the present invention to provide a method and a system for an efficient network motif detection in terms of throughput, energy and memory requirements. This object is solved by a method and a system defined in the independent claims. Preferred embodiments are subject of the dependent claims.